package com.lqian.simplestructure.sorted;

import java.util.Arrays;

/**
 * 选择排序：找出数组中最小的元素，并将其加入新数组中
 */
public class SelectedSort {

    public static void main(String[] args) {
        int[] arr = {2,4,2,7,5,1,9,5,6};
//
//        int small = findSmall(arr);
//        System.out.println(small);

        selectedSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    //找到存储最小值索引
    public static int findSmall(int[] arr){
        int smallest_target = arr[0];
        int smallest_index = 0;
        for (int i = 1;i < arr.length; i++){
            //如果后一个数比当前记录的最小值还要小
            if (arr[i] < smallest_target){
              smallest_target = arr[i];
              smallest_index = i;
            }
        }
        return smallest_index;
    }

    public static void selectedSort(int[] arr){
        //循环遍历比较
        for (int i = 0; i <arr.length ; i++) {
            //假设第一个元素的下标是最小的
            int smallestIndex = i;
            //与后面的值比较
            for (int j = i+1; j <arr.length ; j++) {
                if (arr[smallestIndex] > arr[j]){
                    smallestIndex = j;
                }
            }
            //如果第一轮 循环都遍历了 最小值的下标不变 代表smallestIndex是当前最小值
            if (smallestIndex != i){
                int temp = arr[i];
                arr[i] = arr[smallestIndex];
                arr[smallestIndex] = temp;
            }

        }
    }
}
